from collections import deque

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0: return True
        if len(s) % 2 == 1: return False
        
        d = deque()
        ret, left = True, ''
        d.appendleft(s[0])
        while len(s) > 0:
            if '}' not in s and ']' not in s and ')' not in s:
                return False
            left = s[0]
            if left == '[' or left == '{' or left == '(':
                d.appendleft(left)
                s = s[1:]
                continue
            top = d.popleft()
            if left == ']' and top == '[' or left == '}' and top == '{' or left == ')' and top == '(':
                s = s[1:]
                continue
            return False
        return ret

if __name__ == '__main__':
    solution = Solution()
    s = ''
    # s = '()[]{}'
    # s = '(]'
    s = '([)])'
    # s = '{[]}'
    # s = '{[}'
    # s = '(([]){})'
    # s = '(('
    s = '))'
    result = solution.isValid(s)
    print(result)
